package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

/**
 * @ClassName Medium_34_SearchRangeInOrderedArray
 * @Description Medium_34_SearchRangeInOrderedArray
 * @Author wanghaiwei
 * @Date 2023/2/16 11:27
 */
public class Medium_34_SearchRangeInOrderedArray {

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        if (nums[nums.length - 1] < target || nums[0] > target) {
            return new int[]{-1, -1};
        }
        return new int[]{getLeftBound(nums, target), getRightBound(nums, target)};
    }

    /**
     * 不断搜索左半边的区间，来定位左边界
     *
     * @param nums
     * @param target
     * @return
     */
    private int getLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBound = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid - 1;
                if (nums[mid] == target) {
                    leftBound = mid;
                }
            } else {
                left = mid + 1;
            }
        }
        return leftBound;
    }

    /**
     * 不断搜索右半边的区间，来定位右边界
     *
     * @param nums
     * @param target
     * @return
     */
    private int getRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBound = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] <= target) {
                left = mid + 1;
                if (nums[mid] == target) {
                    rightBound = mid;
                }
            } else {
                right = mid - 1;
            }
        }
        return rightBound;
    }

    public static void main(String[] args) {
        Medium_34_SearchRangeInOrderedArray solution = new Medium_34_SearchRangeInOrderedArray();
        String result = StringUtils.join(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8), ',');
        Assert.isTrue("3,4".equals(result), "nums = [5,7,7,8,8,10], target = 8 计算错误，预期[3,4]，实际：" + result);
        result = StringUtils.join(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6), ',');
        Assert.isTrue("-1,-1".equals(result), "nums = [5,7,7,8,8,10], target = 6 计算错误，预期[-1,-1]，实际：" + result);
        result = StringUtils.join(solution.searchRange(new int[]{}, 0), ',');
        Assert.isTrue("-1,-1".equals(result), "nums = [], target = 0 计算错误，预期[-1,-1]，实际：" + result);
    }
}
